package 动态规划;

/**
 * 5:最长回文子串
    给你一个字符串 s，找到 s 中最长的回文子串
 思路：采用动态规划的方法解决
    1：创建一个二维数组dp,dp[i][j] 表示字符串s中从下标i到下标j的字符串是否为回文串，
        如果 dp[i][j] 为 true，表示子串是从 i 到 j 的回文子串。
    2:状态方程的定义，
        当前位上dp[i][j] 是否为回文串的定义取决于其子串是否为回文串，且当前左右两侧位上的元素是否相同，s[i] == s[j]
    所以状态转移方程为：dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
        - 如果 s[i] == s[j] 且子串的长度小于 3（即 j - i < 2），则 dp[i][j] = true。
        - 如果 s[i] == s[j] 且子串的长度大于等于 3，则 dp[i][j] = dp[i+1][j-1]。
    3:边界条件的定义：
        所有长度为 1 的子串都是回文，即 dp[i][i] = true。
        按照子串的长度进行填充
    4:跟踪最长回文子串：
    在填充动态规划数组的过程中，记录最长回文子串的起始位置和长度。
 */
public class L_5 {
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return "";

        int max = 1;
        int start = 0;
        boolean[][] dp = new boolean[n][n];

        // 长度为1的都是回文串
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                dp[i][j] = true;
            }
        }
        // 长度为2的子串处理
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)){
                dp[i][i+1] = true;
                max = 2;
                start = i;
            }
        }
        // 长度大于2的子串处理
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i+len <= n ; i++) {
                int j = i+len-1;
                if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]){
                    dp[i][j] = true;
                    max = len;
                    start = i;
                }
            }
        }
        return s.substring(start,start+max);
    }
}
